{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Nodes Equal to Sum of Descendants"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: equalToDescendants"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #值等于子节点值之和的节点数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一颗二叉树的根节点&nbsp;<code>root</code>&nbsp;，返回满足条件：节点的值等于该节点所有子节点的值之和&nbsp;<em>的节点的数量。</em></p>\n",
    "\n",
    "<p>一个节点&nbsp;<code>x</code>&nbsp;的&nbsp;<strong>子节点</strong>&nbsp;是指从节点&nbsp;<code>x</code>&nbsp;出发，到所有叶子节点路径上的节点。没有子节点的节点的子节点和视为&nbsp;<code>0</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/17/screenshot-2021-08-17-at-17-16-50-diagram-drawio-diagrams-net.png\" style=\"width: 250px; height: 207px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [10,3,4,2,1]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "对于值为10的节点: 其子节点之和为： 3+4+2+1 = 10。\n",
    "对于值为3的节点：其子节点之和为： 2+1 = 3。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/17/screenshot-2021-08-17-at-17-25-21-diagram-drawio-diagrams-net.png\" style=\"height: 196px; width: 200px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [2,3,null,2,null]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "没有节点满足其值等于子节点之和。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/17/screenshot-2021-08-17-at-17-23-53-diagram-drawio-diagrams-net.png\" style=\"width: 50px; height: 50px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [0]\n",
    "<strong>输出:</strong> 1\n",
    "<strong>解释:</strong>\n",
    "对于值为0的节点：因为它没有子节点，所以自己点之和为0。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数量范围：&nbsp;<code>[1, 10<sup>5</sup>]</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-nodes-equal-to-sum-of-descendants](https://leetcode.cn/problems/count-nodes-equal-to-sum-of-descendants/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-nodes-equal-to-sum-of-descendants](https://leetcode.cn/problems/count-nodes-equal-to-sum-of-descendants/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,3,4,2,1]', '[2,3,null,2,null]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        cnt = 0\n",
    "        def dfs(root) -> int:\n",
    "            nonlocal cnt\n",
    "            if not root: return 0\n",
    "            leftSum = dfs(root.left)\n",
    "            rightSum = dfs(root.right)\n",
    "            if leftSum + rightSum == root.val:\n",
    "                cnt += 1\n",
    "            return leftSum + rightSum + root.val\n",
    "        dfs(root)\n",
    "        return cnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=0\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            ret=0\n",
    "            if node.left:\n",
    "                ret+=dfs(node.left)\n",
    "            if node.right:\n",
    "                ret+=dfs(node.right)\n",
    "            if node.val==ret:\n",
    "                ans+=1\n",
    "            ret+=node.val\n",
    "            return ret\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(root):\n",
    "            if root is None: return 0\n",
    "            res = dfs(root.left) + dfs(root.right)\n",
    "            if res == root.val:\n",
    "                self.ans += 1\n",
    "            return res + root.val\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            if node is None:\n",
    "                return 0\n",
    "\n",
    "            tot = dfs(node.left) + dfs(node.right)\n",
    "            if tot == node.val:\n",
    "                ans += 1\n",
    "\n",
    "            return tot + node.val\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = []\n",
    "\n",
    "        def search(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            sum_l = search(root.left)\n",
    "            sum_r = search(root.right)\n",
    "            if root.val == sum_l + sum_r:\n",
    "                ans.append(True)\n",
    "            return root.val + sum_l + sum_r\n",
    "        \n",
    "        search(root)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        self.result = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0        \n",
    "\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "           \n",
    "            if left + right == node.val:\n",
    "                self.result += 1\n",
    "            \n",
    "            return left + right + node.val\n",
    "\n",
    "        dfs(root)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        result = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal result\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            if root.val == left + right:\n",
    "                result += 1\n",
    "            return root.val + left + right\n",
    "\n",
    "        dfs(root)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans \n",
    "            if not node:\n",
    "                return 0\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            if node.val == l + r:\n",
    "                ans += 1\n",
    "            return l + r + node.val \n",
    "        \n",
    "        dfs(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def equalToDescendants(self, root: Optional[TreeNode]) -> int:\n",
    "        # Initialize the counter for nodes that satisfy the condition\n",
    "        self.count = 0\n",
    "        \n",
    "        # Helper function to perform DFS and return the sum of the subtree rooted at 'node'\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            # Calculate the sum of the left and right subtrees\n",
    "            left_sum = dfs(node.left)\n",
    "            right_sum = dfs(node.right)\n",
    "            \n",
    "            # Check if the value of the current node equals the sum of its descendants\n",
    "            if node.val == left_sum + right_sum:\n",
    "                self.count += 1\n",
    "            \n",
    "            # Return the sum of the subtree rooted at 'node'\n",
    "            return node.val + left_sum + right_sum\n",
    "        \n",
    "        # Start the DFS from the root\n",
    "        dfs(root)\n",
    "        \n",
    "        return self.count\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
